package org.algorithm.greedy;

import java.util.*;

public class GreedyAlgorithm {
    public static void main(String[] args) {

        HashSet<String> set1 = new HashSet<>();
        set1.add("北京");
        set1.add("上海");
        set1.add("天津");

        HashSet<String> set2 = new HashSet<>();
        set2.add("广州");
        set2.add("北京");
        set2.add("深圳");

        HashSet<String> set3 = new HashSet<>();
        set3.add("成都");
        set3.add("上海");
        set3.add("杭州");

        HashSet<String> set4 = new HashSet<>();
        set4.add("上海");
        set4.add("天津");

        HashSet<String> set5 = new HashSet<>();
        set5.add("杭州");
        set5.add("大连");

        HashSet<String> AllArea = new HashSet<>();

        AllArea.addAll(set1);
        AllArea.addAll(set2);
        AllArea.addAll(set3);
        AllArea.addAll(set4);
        AllArea.addAll(set5);

        AllArea.forEach(System.out::println);

        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        broadcasts.put("k1", set1);
        broadcasts.put("k2", set2);
        broadcasts.put("k3", set3);
        broadcasts.put("k4", set4);
        broadcasts.put("k5", set5);

        List<String> selects = new ArrayList<>();
        String maxKey = null;
        HashSet<String> tempSet;
        while (AllArea.size() > 0) {

            for (String k : broadcasts.keySet()) {
                tempSet = broadcasts.get(k);
                tempSet.retainAll(AllArea);
                if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
                    maxKey = k;
                }
            }
            if (maxKey != null) {
                selects.add(maxKey);
                AllArea.removeAll(broadcasts.get(maxKey));
            }

            //  tempSet.clear();
            maxKey = null;
        }


        System.out.println(selects);
    }


}
